package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

/**
 * LC701.二叉搜索树中的插入操作
 */
public class LC701 {
    public TreeNode insertIntoBST(TreeNode root, int val) { //递归解法
        TreeNode curr = root;
        TreeNode prev = null;
        while (curr != null) {
            prev = curr;
            if (curr.val > val) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        if (prev == null) {
            return new TreeNode(val);
        } else {
            if (prev.val > val) {
                prev.left = new TreeNode(val);
            } else {
                prev.right = new TreeNode(val);
            }
            return root;
        }
    }
    public TreeNode insertIntoBSTD(TreeNode root, int val) { //迭代法
        if (root == null) return new TreeNode(val);
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }

    public static void main(String[] args) {
        LC701 alg = new LC701();
        TreeNode root1 = new TreeNode(1, null, new TreeNode(2));
        root1.right.left = new TreeNode(2);
    }
}
